import com.sun.xml.internal.messaging.saaj.util.TeeInputStream;
import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class BinaryTree {

     class TreeNode{
          public  int val;
           public TreeNode left;
           public TreeNode right;
          public TreeNode(int val){
              this.val=val;
          }
       }

       public TreeNode root;  //根节点

    public void creatTree(){
       root = new TreeNode(10);
        TreeNode s2 = new TreeNode(15);
        TreeNode s3=new TreeNode(19);
        TreeNode s4=new TreeNode(25);
        TreeNode s5=new TreeNode(18);
        TreeNode s6=new TreeNode(34);
        TreeNode s7=new TreeNode(65);
        TreeNode s8=new TreeNode(49);
        TreeNode s9=new TreeNode(27);
        TreeNode s10=new TreeNode(37);
        TreeNode s11=new TreeNode(28);
        root.left=s2;
        root.right=s3;
        s2.left=s4;
        s2.right=s5;
        s3.left=s6;
        s3.right=s7;
        s4.left=s8;
        s4.right=s9;
        s5.left=s10;
        s5.right=s11;
    }

    public ArrayList<Integer> CenterTree2(){
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> arrayList = new ArrayList<>();
        TreeNode p = root;

        while(p!=null||!stack.empty()){

            while(p!=null){
                stack.push(p);
                p=p.left;
            }
            if(!stack.empty()){
                TreeNode tmp = stack.pop();
                arrayList.add(tmp.val);
                p=tmp.right;
            }

        }
        return arrayList;
    }

    public ArrayList<Integer> FirstTree2() {
        TreeNode cur = root;
        ArrayList<Integer> arrayList = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return arrayList;
        }
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                arrayList.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            if (!stack.empty()) {
                TreeNode tmp = stack.pop();
                cur = tmp.right;
            }

        }
        return arrayList;

    }
    public void FirstTree(){
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        if(root==null){
            return;
        }
        stack1.push(root);
        while(!stack1.empty()){
            TreeNode tmp = stack1.pop();
            if(tmp.left==null&&tmp.right==null){
                System.out.print(tmp.val+" ");
                continue;
            }
            if(tmp.left==null){
                stack2.push(tmp.right);
            }else if(tmp.right==null){
                stack1.push(tmp.left);
            }else{
                stack1.push(tmp.left);
                stack2.push(tmp.right);
            }
            System.out.print(tmp.val+" ");
        }
        while(!stack2.empty()){
            TreeNode tmp = stack2.pop();
            while(!stack1.empty()){
                TreeNode tp = stack1.pop();

                if(tp.left==null&&tp.right==null){
                    System.out.print(tp.val+" ");
                    continue;
                }
                if(tp.left==null){
                    stack2.push(tp.right);
                }else if(tp.right==null){
                    stack1.push(tp.left);
                }else{
                    stack1.push(tp.left);
                    stack2.push(tp.right);
                }
            }
            if(tmp.left==null&&tmp.right==null){
                System.out.print(tmp.val+" ");
                continue;
            }
            if(tmp.left==null){
                stack2.push(tmp.right);
            }else if(tmp.right==null){
                stack1.push(tmp.left);
            }else{
                stack1.push(tmp.left);
                stack2.push(tmp.right);
            }
            System.out.print(tmp.val+" ");
        }

    }

    public ArrayList<Integer> FirstTree3() {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if (root == null) {
            return arrayList;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null||!stack.empty()) {
            while (cur != null) {
                arrayList.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode tmp = stack.pop();
            cur = tmp.right;

        }
        return arrayList;
    }

    public void midTree(){
        if(root==null){
            return;
        }
        TreeNode cur = root;
        Stack<TreeNode>stack = new Stack<>();
        while(cur!=null||!stack.empty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode tmp = stack.pop();
            System.out.print(tmp.val+" ");
            cur=tmp.right;
        }
    }

    public ArrayList<Integer> postTree(){
        ArrayList<Integer> arrayList =new ArrayList<>();
        if(root==null){
            return arrayList;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur=root;
        TreeNode prev= null;
        while(cur!=null||!stack.empty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }

            TreeNode tmp = stack.peek();

            if(tmp.right==null||tmp.right==prev){
                arrayList.add(tmp.val);
                 prev=tmp;
                 stack.pop();
            }else {
                cur = tmp.right;
            }
        }
    }
}
